package acwing.sort;

import java.util.Scanner;

/**
 * 给定一个长度为 n
 *  的整数数列，以及一个整数 k
 * ，请用快速选择算法求出数列从小到大排序后的第 k
 *  个数。
 *
 * 输入格式
 * 第一行包含两个整数 n
 *  和 k
 * 。
 *
 * 第二行包含 n
 *  个整数（所有整数均在 1∼109
 *  范围内），表示整数数列。
 *
 * 输出格式
 * 输出一个整数，表示数列的第 k
 *  小数。
 *
 * 数据范围
 * 1≤n≤100000
 * ,
 * 1≤k≤n
 *
 * 输入样例：
 * 5 3
 * 2 4 1 5 3
 * 输出样例：
 * 3
 */
public class KstNumber_ {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        KstNumber(arr,0,arr.length - 1);
        System.out.println(arr[k - 1]);
    }
    public static void KstNumber(int[] arr,int left,int right) {
        // 剪枝
        if (left >= right)  return;
        // 1. 选择中间数
        int x = arr[(left + right) / 2];
        // 2. 排序
        int i = left - 1;
        int j = right + 1;
        while (i < j){
            while(arr[++i] < x);
            while(arr[--j] > x);
            if (i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 3. 递归
        KstNumber(arr,left,j);
        KstNumber(arr,j + 1,right);
    }
}
